#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
// 单词拆分：https://leetcode.cn/problems/word-break/
using namespace std;
class Solution {
public:
    //1.状态表示： dp[i]: [0,i]位置的字符串，能否被拼出
    //            j:记录最后一个字符的起始位置
    //2.状态转移方程： dp[i]=(dp[j-1]&&find(substr(j,i-j+1))==true)
    //3.初始化： dp[0]=true,j=1
    bool wordBreak(string s, vector<string>& wordDict) {
        s='*'+s;
        unordered_map<string,int> hash;
        for(auto x:wordDict) hash[x]++;
        int n=s.size();
        vector<bool> dp(n+1,false);
        dp[0]=true;
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j>=1;j--)
            {
                dp[i]=dp[j-1]&&(hash.count(s.substr(j,i-j+1)));
                if(dp[i]==true) break;
            }
        }
        return dp[n];
    }
};